Solid state memories or devices (also known as SSDs) store data, for example into a NAND-based flash memory. Operations performed on a SSD such as read and write operations are controlled by a solid-state memory controller or flash memory controller. Before writing new data on a segment of a SSD, data already written on the segment must be erased before new data can be overwritten. These memories can only sustain a limited number of erase-write cycles, usually between 10,000 and 1,000,000, which is commonly known as the endurance of these devices. Endurance is a critical design criterion for measuring the reliability of SSDs.
Flash memories are organized into a number of erase blocks or sectors and each must be erased prior to writing data. A typical erase block is 256 KB in size, however may range from 128 KB to 2,048 KB or even more. Any given address within an erase block cannot be rewritten without an intervening erase. Erase cycles are cumulative and affect only those erase blocks being cycled. In other words, an error in any erase block is constrained to the data of that block. Erase cycles range from 10,000 to 1,000,000, depending on vendor's manufacturing process.
Wear-leveling is a common technique used to prolong the lifetime of SSDs. This function is normally implemented in the solid-state memory controller or flash memory controller. Wear-leveling allows data writes to be evenly distributed over the entire storage media. More precisely, wear-leveling is an algorithm by which the controller in the storage device evens out the overall wear among all Flash blocks, e.g. by re-maping logical block addresses to different physical block addresses in the SSD.
There are a lot of existing wear-leveling algorithms in the prior art. They focus on utilizing every flash block evenly. These algorithms differs from each other mainly in terms of the frequency of block re-mapping, the algorithm to find the “least worn” blocks to which to write and variations of data block swapping capabilities. Depending on whether static data blocks are moved around or not, these algorithms can be classified into two categories: dynamic wear-leveling and static wear-leveling. A wear-leveling algorithm is called dynamic if it does not move around static data blocks, otherwise it is called static.
All the existing wear-leveling algorithms, either dynamic or static, operate at the block level, namely they aim to balance erase/write operations on all flash blocks available in the SSD. However, the actual wear caused to any specific cell is proportional to the number of 0s ever being written to it. For example, if flash cells have an endurance specification of 10,000 erase/write cycles, each cell can therefore be erased and written 10,000 times with 0s. Therefore, since chunks of data that are written to flash blocks can be seen as being random, hence not necessarily having the same number of 0s, flash blocks may likely experience significantly different levels of wear due to the varying number of 0s being written onto them, thereby leading to portion of blocks being worn out much earlier than others.
Hence, the drawback of block-level wear-leveling arises mainly due to the fact that different data blocks may impose different wear on flash blocks, and thus the actual wear on any two blocks can be significantly different even though both have exactly the same number of erase-write operations.
Since a flash cell is the minimum memory unit which can potentially lead to a failure of the whole block, a cell-based wear-leveling algorithm that tracks and controls the wear of individual memory cells is desirable.